CADENAS DE MARKOV

ANDRÉI MARKOV

 

Riazán, 1856 - San Petersburgo, 1922) Matemático ruso que desarrolló la moderna teoría de procesos estocásticos. Trabajó en la casi totalidad de los campos de la matemática. En el campo de la la teoría de la probabilidad, profundizó en las consecuencias del teorema central del límite y en la ley de los grandes números. En su honor, lleva su nombre un tipo muy especial de procesos estocásticos.

Markov, graduado en la Universidad de San Petersburgo en 1878, fue alumno de Pafutny Chebyshev, quien ejerció una gran influencia en sus investigaciones. Impartió clases de matemáticas en esta Universidad desde 1886. Sus primeras investigaciones versaron sobre análisis y teoría de números, en particular sobre las fracciones continuas, límites de integrales, teoría de aproximaciones y convergencia de series. En 1900 estudió la teoría de probabilidades. Demostró a partir de supuestos muy generales el llamado teorema central del límite, que establece que la suma de un número grande de variables aleatorias independientes se aproxima a una distribución Gaussiana.

Tras este trabajo, estudió las variables dependientes e introdujo el concepto de sucesos encadenados. Markov extendió los resultados clásicos de sucesos independientes a cierto tipo de sucesos encadenados, conocidos como sucesos markovianos, que son aquellos cuyo estado en un instante de tiempo depende de uno o varios estados cronológicamente anteriores. Este estudio, desarrollado por su discípulo Andrei Kolmogorov y por Norbert Wiener, se convirtió en una teoría general de procesos estocásticos y se ha aplicado con éxito en campos tan dispares como la biología, la sociología y la lingüística.

 

CADENAS DE MARKOV

Una cadena de Markov es un tipo especial de proceso discreto en el tiempo. Se supone que en cualquier instante el proceso estocástico discreto en el tiempo puede estar en un número infinito de estados identificados con 1,2…n.

Las cadenas de markov son modelos probabilísticos que se usan para predecir la evolución y el comportamiento a corto y a largo plazo de determinados sistemas. Una cadena de markov, por tanto,  representa un sistema que varía su estado a lo largo del tiempo, siendo cada cambio una transición del sistema.

Los estados son una caracterización de la situación en que se halla el sistema en un instante dado. El estado en un sistema t es una variable cuyos valores solo pueden pertenecer al conjunto de estados del sistema. El sistema modelizado por la cadena es, por tanto, una variable que cambia de valor en el tiempo, cambio al que llamamos transición. Por ser el sistema estocástico, no se conocerá con certeza el estado del sistema en un determinado instante, sino tan solo la probabilidad asociada a cada uno de los estados.

CADENAS DE MARKOV : CONCEPTOS

MATRIZ DE TRANSICIÓN

Esta es una matriz  cuadrada, donde el número de renglones y de columnas será igual al de estados que tenga la cadena de Markov, siendo cada elemento de la matriz, la probabilidad de transición respectiva de pasar del estado que encabeza el renglón donde está ubicado el elemento hacia el estado encabezado por la columna.

Miremos el siguiente ejemplo:

Se observa que para el primer renglón las probabilidades de transición indican que habrá un 50% de los clientes fieles a la marca A, por su parte un 30% cambiara de A a  B y un 20% cambiara de A a C. Obsérvese que la suma se probabilidades de cada renglón es igual a 1.

Una manera de visualizar mejor la tabla dada anteriormente es a través de un diagrama de estado. Aquí los estados se indican a través de círculos y las flechas que salen de ellos son las probabilidades de que sus clientes cambien a otro estado. Es decir, las flechas que regresan al mismo estado del que salen, señalan las probabilidades de que los clientes sean retenidos por esa marca en particular.

CALCULO DE PROBABILIDADES DE LA MATRIZ DE TRANSICIÓN

Para hallar las probabilidades de los estados dentro de la matriz de transición en un periodo determinado procedemos de la siguiente manera como se muestra en el siguiente ejemplo:

Las granjas de cierta región se pueden clasificar con 3 tipos: agrícolas, pecuarias o mixtas. Actualmente 30% son agrícolas, 40% pecuarias y 30% son mixtas. La matriz de transición de un año al siguiente es:

De acuerdo a la información dada, el Po es:

Para hallar el valor de las probabilidades en el año siguiente hacemos uso de la multiplicación de las matrices, como sigue

Para el estado A:

Por lo que el vector para el año siguiente es:

De igual manera calculamos el porcentaje para cada tipo de granja para el periodo 2, 3, 4 y 5



Obsérvese que el valor de la probabilidad de un estado n esta dado por la siguiente expresión:



MATRIZ DE TRANSICIÓN EN ESTADO ESTABLE

Un estado es estable cuando ya no hay cambios en el sistema, es decir que se alcanza el equilibrio. Una manera posible de obtener las condiciones del sistema para el estado estable es repetir iterativamente los cálculos para cada periodo con el fin de hallar el periodo con aquellas probabilidades que se mantienen constantes o no cambian.

Sin embargo también es posible utilizar los métodos para resolver sistemas de ecuaciones que nos permiten encontrar directamente estas probabilidades de estado estables.

Dado el ejemplo anterior acerca de los tipos de granjas, calcularemos los estados estables a través de los métodos para sistemas de ecuaciones.

En primera medida lo que hacemos es hallar la traspuesta de la matriz de transición, es decir:

El sistema de ecuaciones quedaría así:

Esta ultima ecuación es agregada siguiendo la propiedad de que la sumatoria las probabilidades de los estados debe ser igual a 1.

Utilizando el método de eliminación, restamos las ecuaciones (1) y (2) eliminando z.

Ahora sumamos las ecuaciones (3) y (4), multiplicando la ecuación 4 por 0.2 con el fin de eliminar z

Despejando de la ecuación (6) y y reemplazando en (5), tenemos:

Reemplazando x en (6)

MATRIZ REGULAR Y MATRIZ ERGODICA

Una  matriz de transición T se dice que es regular si para algún elemento positivo de k la matriz T^k no tiene elementos iguales a cero. Además debe tener comunicación directa con los demás estados.

Si los estados de una cadena  son recurrentes, aperiódicos y se comunican entre sí, se dice que la matriz es ergódica.

CLASIFICACION DE LOS ESTADOS DE LA CADENA DE MARKOV

Los estados de una cadena de Markov se clasifican dependiendo de la fracción de tiempo que la cadena pasa en cada uno de ellos.

Los estados de una cadena de Markov pueden ser:

Ø  Transitorios: Un estado es transitorio si después de haber entrado a este estado, el proceso no regresara a él.

Ø  Recurrentes: Se dice que un estado es recurrente si después de haber entrado a este estado el proceso definitivamente regresara a ese estado. Por consiguiente, un estado es recurrente si y solo si no es transitorio.

Ø  Absorbentes: Un estado se llama absorbente si después de haber entrado ahí el proceso nunca saldrá de ese estado. Por consiguiente, el estado i es un estado absorbente si y solo si Pij=1.

 

ESTADOS ABSORBENTES

Se dice que un estado es absorbente si es cero la probabilidad de hacer una transición fuera de ese estado. Por tanto, una vez que el sistema hace una transición hacia un estado absorbente, permanece en el siempre

MATRIZ FUNDAMENTAL

La matriz fundamental es muy útil para el análisis y solución de situaciones en las cuales aparecen estados absorbentes.

La metodología para obtener la matriz fundamental es la siguiente:

1.      Obtener la matriz de transición en la forma usual, incluyendo los estados absorbentes.

2.      Identificar de la matriz de transición los renglones correspondientes a la matriz absorbente

3.      De lo que ha quedado de la matriz de transición en el paso anterior, dividirlo en dos partes: N que será la parte no absorbente y A que contendrá los estados absorbentes

4.      Obtenemos la matriz U mediante la siguiente fórmula:

U=I-N

Donde I es la matriz identidad.

5.      Finalmente, se obtiene la matriz identidad de la siguiente manera:

X=U^-1

Donde X representa la inversa de U, la cual se obtiene por algunos métodos como el Gauss- Jordan.

Veamos el siguiente ejemplo en el cual explicaremos algunos conceptos importantes:

Una empresa  emplea a tres tipos de ingenieros: principiantes, con experiencia  y socios. Durante un año determinado hay una probabilidad de 0.15 que un ingeniero principiante sea ascendido a ingeniero con experiencia y una probabilidad de 0.05 que deje la empresa sin ser socio. También hay una probabilidad de 0.20 que un ingeniero con experiencia sea ascendido a socio y una probabilidad de 0.10 que deje la empresa sin ser socio. También hay una probabilidad de 0.05 de que un socio deje la empresa. Determine:

a)   ¿Cuál es la duración promedio de un ingeniero recién contratado?

b)   ¿cuál es la probabilidad de que un ingeniero principiante llegue a ser socio?

c)   ¿Cuál es la duración promedio que pasa un socio en la empresa?

Primero, determinamos la matriz de transición en la cual se observa que hay dos estados absorbentes: el ingeniero deje la empresa sin ser socio y que un socio deje la empresa

Donde IP= INGENIERO PRINCIPIANTE

IE= INGENIERO CON EXPERIENCIA

IS  = INGENIERO SOCIO

IDS= INGENIERO DEJA LA EMPRESA SIENDO SOCIO

IDSS= INGENIERO DEJA LA EMPRESA SIN SER SOCIO

Luego hallamos la matriz I-N, donde I es la matriz de identidad y N la matriz no absorbente identificada en el paso anterior.

Luego a través de Gauss-Jordan, hallamos la matriz inversa como se muestra a continuación.

Para responder la primera pregunta debemos tener presente un nuevo concepto que es el valor esperado que es el tiempo en que un estado demora antes de ser absorbido. Este valor esperado se obtiene a través de la matriz inversa. De esta forma, la duración promedio de un recién contratado seria:

Para hallar la probabilidad de que un ingeniero principiante llegue a ser socio se debe multiplicar la matriz inversa por la matriz absorbente, de la siguiente manera:

Obsérvese que esta probabilidad es igual a 0.5.

De igual manera como en la primera parte, la duración promedio de un socio en la empresa es:

Tomado de Fundamentos de Investigación de operaciones de Administración:

http://books.google.com/books?id=CL3E0b_6F_cC&pg=PA45&dq=demanda+probabilistica&hl=es&ei=vwnwTb66Ho63tgfuyo28CQ&sa=X&oi=book_result&ct=result&resnum=5&ved=0CEAQ6AEwBA#v=onepage&q&f=false